class Node:  
    """默认构造函数"""  
    def __init__(self, value = None, next_node=None):  
        self.value = value    # 节点的值  
        self.next = next_node # 指向下一个节点的引用 
    

class LinkedList:  
    """定义链表"""  
    def __init__(self):  
        self.head = None # 链表的头节点 

    # 头插  
    def push_front(self, value):  
        """在链表头部插入一个新节点"""  
        new_node = Node(value)  
        new_node.next = self.head # 新节点的 next 指向当前头节点  
        self.head = new_node      # 更新头节点为新节点  
  
    # 头删  
    def pop_front(self):  
        """删除链表头部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        res = self.head.value      # 获取要删除节点的值  
        self.head = self.head.next # 更新头节点为下一个节点  
        return res  
  
    # 尾插  
    def push_back(self, value):  
        """在链表尾部插入一个新节点"""  
        new_node = Node(value)  
        if self.head is None:    # 如果链表为空，新节点成为头节点  
            self.head = new_node  
        else:  
            curr = self.head     # 遍历到链表尾部
            while curr.next is not None:    
                curr = curr.next  
            curr.next = new_node # 在尾部插入新节点  
  
    # 尾删  
    def pop_back(self):  
        """删除链表尾部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        if self.head.next is None: # 如果链表只有一个节点  
            res = self.head.value  
            self.head = None       # 清空头节点  
            return res
          
        curr = self.head           # 遍历到倒数第二个节点
        while curr.next.next is not None:    
            curr = curr.next  
        res = curr.next.value      # 获取要删除节点的值  
        curr.next = None           # 删除尾节点  
        return res  
    
    # 查找
    def search(self, target):  
            """查找链表中第一个值为target的节点，并返回其节点对象"""  
            curr = self.head  
            while curr is not None:  
                if curr.value == target:  
                    return curr # 返回找到的节点对象  
                curr = curr.next  
            return None         # 如果未找到，返回None
  
    # 修改  
    def update(self, old_value, new_value):    
        """修改链表中第一个值为old_value的节点的值为new_value，并返回是否成功修改"""    
        node = self.search(old_value) # 查找节点    
        if node is not None:    
            node.value = new_value    
            return True               # 修改成功    
        return False                  # 未找到要修改的节点 
  
    # 打印  
    def print_list(self):  
        """打印链表中的所有节点值"""  
        curr = self.head  
        while curr is not None:  
            print(f"{curr.value}->", end="")  
            curr = curr.next  
        print("None")  

# 合并两个有序链表
def merge_two_sorted_lists(l1: LinkedList, l2: LinkedList) -> LinkedList:  
    """  
    将两个升序链表合并为一个新的升序链表并返回。  
    """  
    # 创建一个新的链表用于存储合并后的结果  
    merged_list = LinkedList()  
    # 初始化两个指针分别指向两个链表的头节点  
    p1 = l1.head  
    p2 = l2.head  
      
    # 遍历两个链表，直到其中一个链表遍历完  
    while p1 is not None and p2 is not None:  
        if p1.value <= p2.value:  
            # 将较小的节点添加到新链表中  
            new_node = Node(p1.value)  
            if merged_list.head is None:  
                merged_list.head = new_node  
                current = merged_list.head  
            else:  
                current.next = new_node  
                current = new_node  
            p1 = p1.next  
        else:  
            # 将较大的节点添加到新链表中  
            new_node = Node(p2.value)  
            if merged_list.head is None:  
                merged_list.head = new_node  
                current = merged_list.head  
            else:  
                current.next = new_node  
                current = new_node  
            p2 = p2.next  
      
    # 如果第一个链表还有剩余节点，添加到新链表中  
    while p1 is not None:  
        new_node = Node(p1.value)  
        current.next = new_node  
        current = new_node  
        p1 = p1.next  
      
    # 如果第二个链表还有剩余节点，添加到新链表中  
    while p2 is not None:  
        new_node = Node(p2.value)  
        current.next = new_node  
        current = new_node  
        p2 = p2.next  
      
    return merged_list  

# 示例用法  
if __name__ == "__main__": 

    l1 = LinkedList()  
    for i in [1, 2, 4]:
        l1.push_back(i)   
    l2 = LinkedList()  
    for i in [1, 3, 4]:
        l2.push_back(i)  

    # 合并两个链表并打印 
    l1.print_list()
    l2.print_list()
    merge_two_sorted_lists(l1, l2).print_list()
    print()

  
    l3 = LinkedList()  
    for i in [1, 1, 2, 4, 5, 7]:
        l3.push_back(i) 
    l4 = LinkedList()  
    for i in [1, 3, 4, 5]:
        l4.push_back(i)  

    # 合并两个链表并打印 
    l3.print_list()
    l4.print_list()
    merge_two_sorted_lists(l3, l4).print_list()
    print()

  
    l5 = LinkedList()  
    for i in [1, 2, 4]:
        l5.push_back(i)    
    l6 = LinkedList()  
    for i in [1, 3, 4, 7, 9]:
        l6.push_back(i)  

    # 合并两个链表并打印 
    l5.print_list()
    l6.print_list()
    merge_two_sorted_lists(l5, l6).print_list()
    print()